package com.wangwei.basic;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Stack;

/**
 * Dijkstra双栈算法
 */
public class Evaluate {
    public static void main(String[] args) {
        String str ="(1+((2+3)*(4*5)))";

        Stack<String> ops = new Stack<>();
        Stack<Double> vals =new Stack<>();
//        while(!StdIn.isEmpty()){
        for(int i =0; i<str.length();i++){
            String s = (char)str.getBytes()[i] +"";
//            String s = StdIn.readString();
            if     (s.equals("("))            ;
            else if(s.equals("+")) ops.push(s);
            else if(s.equals("-")) ops.push(s);
            else if(s.equals("*")) ops.push(s);
            else if(s.equals("/")) ops.push(s);
            else if(s.equals("sqrt")) ops.push(s);
            else if(s.equals(")")) {
                String op = ops.pop();
                double v =vals.pop();
                if      (op.equals("+"))    v= vals.pop() + v;
                else if (op.equals("-"))    v= vals.pop() - v;
                else if (op.equals("*"))    v= vals.pop() * v;
                else if (op.equals("/"))    v= vals.pop() / v;
                else if (op.equals("sqrt")) v= Math.sqrt(v);
                vals.push(v);
            }//如果字符串即非运算符也不是括号，将它作为double值压入栈。
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}
